package com.example.leetcode.stack.common;

import com.example.leetcode.array.common.ArrayUtils;
import com.example.leetcode.linkedlist.common.ListNode;

import java.util.*;

public class StackUtils {
    public static boolean isValid(String s) {
        char[] array = s.toCharArray();
        Stack<String> stack = new Stack<>();
        for (char c : array) {
            // 碰到左括号，直接进栈
            if (c == '(' || c == '[' || c == '{') {
                stack.push(String.valueOf(c));
            }
            // 以下是右括号
            if (c == ')') {
                if (!stack.isEmpty() && stack.peek().equals("(")) {
                    stack.pop();
                } else {
                    return false;
                }
            }
            if (c == ']') {
                if (!stack.isEmpty() && stack.peek().equals("[")) {
                    stack.pop();
                } else {
                    return false;
                }
            }
            if (c == '}') {
                if (!stack.isEmpty() && stack.peek().equals("{")) {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static String removeDuplicateLetters(String s) {
        char[] str = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        // 统计所有字符的出现次数
        for (char value : str) {
            map.merge(value, 1, Integer::sum);
        }
        // 单调递增栈
        Stack<Character> stack = new Stack<>();
        // 标记某个字符是否出现在栈中
        Map<Character, Boolean> show = new HashMap<>();
        for (char c : str) {
            // 如果栈中已经存在当前字符,不再处理
            if (show.getOrDefault(c, false)) {
                // 取出每个字符,剩余字符数减一
                map.merge(c, -1, Integer::sum);
                continue;
            }
            // 如果栈空 或者 栈顶字符后续不再有了 或者栈顶元素字典序先于当前字符, 结束循环不再出栈
            while (!stack.isEmpty() && map.getOrDefault(stack.peek(), 0) > 0 && stack.peek() >= c) {
                show.remove(stack.pop());
            }
            // 由于预先扣减字符,可能出现栈顶元素与当前元素是同一元素的情况,此时计数器map中的数量是0也会导致退出while循环
            stack.push(c);
            show.put(c, true);
            // 取出每个字符,剩余字符数减一
            map.merge(c, -1, Integer::sum);
        }
        StringBuilder result = new StringBuilder();
        while (!stack.isEmpty()) {
            result.insert(0, stack.pop());
        }
        return result.toString();
    }

    /**
     * 使用单调栈来解决
     *
     * @param head
     * @return
     */
    public static int[] nextLargerNodes(ListNode head) {
        if (head.next == null) {
            return new int[]{0};
        }
        Stack<ListNode> stack = new Stack<>();
        ListNode curNode = head;
        stack.push(curNode);
        curNode = curNode.next;
        Map<ListNode, Integer> map = new HashMap<>();
        while (curNode != null) {

            // 栈内单调递减
            while (!stack.isEmpty() && stack.peek().val < curNode.val) {
                ListNode top = stack.pop();
                map.put(top, curNode.val);
            }
            stack.push(curNode);
            curNode = curNode.next;
        }
        while (!stack.isEmpty()) {
            map.put(stack.pop(), 0);
        }
        curNode = head;
        List<Integer> list = new ArrayList<>();
        while (curNode != null) {
            list.add(map.get(curNode));
            curNode = curNode.next;
        }
        return ArrayUtils.convertListToArray(list);
    }

    public static int[] nextLargerNodes2(ListNode head) {
        List<Integer> ans = new ArrayList<Integer>();
        Deque<int[]> stack = new ArrayDeque<int[]>();

        ListNode cur = head;
        int idx = -1;
        while (cur != null) {
            ++idx;
            ans.add(0);
            while (!stack.isEmpty() && stack.peek()[0] < cur.val) {
                ans.set(stack.pop()[1], cur.val);
            }
            stack.push(new int[]{cur.val, idx});
            cur = cur.next;
        }

        int size = ans.size();
        int[] arr = new int[size];
        for (int i = 0; i < size; ++i) {
            arr[i] = ans.get(i);
        }
        return arr;
    }

    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums2) {
            if (stack.isEmpty()) {
                stack.push(num);
                continue;
            }
            while (stack.size() > 0 && stack.peek() < num) {
                map.put(stack.pop(), num);
            }
            stack.push(num);
        }
        while (stack.size() > 0) {
            map.put(stack.pop(), -1);
        }
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            ans[i] = map.get(nums1[i]);
        }
        return ans;
    }

    public static int[] nextGreaterElements(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int[] doubleNums = new int[nums.length * 2];
        int index = 0;
        for (int m = 0; m < 2; m++) {
            for (int num : nums) {
                doubleNums[index] = num;
                index++;
            }
        }
        // 下标对数组长度取模的话就不用像这样显式拉直循环数组了
        int[] ans = new int[doubleNums.length];
        for (int i = 0; i < doubleNums.length; i++) {
            if (stack.isEmpty()) {
                stack.push(i);
                continue;
            }
            while (stack.size() > 0 && doubleNums[stack.peek()] < doubleNums[i]) {
                ans[stack.pop()] = doubleNums[i];
            }
            stack.push(i);
        }
        while (stack.size() > 0) {
            ans[stack.pop()] = -1;
        }
        int[] res = new int[nums.length];
        System.arraycopy(ans, 0, res, 0, nums.length);
        return res;
    }

    public static String removeKdigits(String num, int k) {
        Deque<Character> deque = new LinkedList<>();
        int length = num.length();
        for (int i = 0; i < length; ++i) {
            char digit = num.charAt(i);
            while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) {
                deque.pollLast();
                k--;
            }
            deque.offerLast(digit);
        }
        for (int i = 0; i < k; ++i) {
            deque.pollLast();
        }
        StringBuilder ret = new StringBuilder();
        boolean leadingZero = true;
        while (!deque.isEmpty()) {
            char digit = deque.pollFirst();
            if (leadingZero && digit == '0') {
                continue;
            }
            leadingZero = false;
            ret.append(digit);
        }
        return ret.length() == 0 ? "0" : ret.toString();
    }

    public static boolean find132pattern(int[] nums) {
        int n = nums.length;
        Deque<Integer> d = new ArrayDeque<>();
        int k = Integer.MIN_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            if (nums[i] < k) return true;
            while (!d.isEmpty() && d.peekLast() < nums[i]) {
                // 事实上，k 的变化也具有单调性，直接使用 k = pollLast() 也是可以的
                k = Math.max(k, d.pollLast());
            }
            d.addLast(nums[i]);
        }
        return false;
    }


    public static int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int[] ans = new int[temperatures.length];
        for (int i = 0; i < temperatures.length; i++) {
            if (stack.isEmpty()) {
                stack.push(i);
                continue;
            }
            while (stack.size() > 0 && temperatures[stack.peek()] < temperatures[i]) {
                Integer top = stack.pop();
                ans[top] = i - top;
            }
            stack.push(i);
        }
        return ans;
    }

    public static int maxChunksToSorted(int[] arr) {
        Stack<int[]> stack = new Stack<>();
        for (int num : arr) {
            int max = num;
            int min = num;
            //处理情况一和情况二，进行块的合并
            while (!stack.isEmpty() && (stack.peek()[1] > num || stack.peek()[0] > num)) {
                int[] ints = stack.pop();
                max = Math.max(max, ints[1]);
                min = Math.min(min, ints[0]);
            }
            stack.push(new int[]{min, max});
        }
        return stack.size();
    }

    public static boolean isValid2(String s) {
        if ((s.length() & 1) == 1) {
            return false;
        }
        while (s.contains("()") || s.contains("[]") || s.contains("{}")) {
            s = s.replace("()", "").replace("[]", "").replace("{}", "");
        }
        return s.equals("");
    }
}
